<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>正则表达式</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="正则表达式">正则表达式</h1>
<h1 id="1-10-regular-expression-matching">1. (10. Regular Expression Matching)</h1>
<p><a href="https://leetcode.com/problems/regular-expression-matching/">https://leetcode.com/problems/regular-expression-matching/</a></p>
<pre><code><code><div>Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:
Input:
s = &quot;aa&quot;
p = &quot;a&quot;
Output: false
Explanation: &quot;a&quot; does not match the entire string &quot;aa&quot;.

Example 2:
Input:
s = &quot;aa&quot;
p = &quot;a*&quot;
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes &quot;aa&quot;.

Example 3:
Input:
s = &quot;ab&quot;
p = &quot;.*&quot;
Output: true
Explanation: &quot;.*&quot; means &quot;zero or more (*) of any character (.)&quot;.

Example 4:
Input:
s = &quot;aab&quot;
p = &quot;c*a*b&quot;
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches &quot;aab&quot;.

Example 5:
Input:
s = &quot;mississippi&quot;
p = &quot;mis*is*p*.&quot;
Output: false
</div></code></code></pre>
<h2 id="11-我的第一个版本-from-top-to-down-dfs--memo">1.1 我的第一个版本, from top to down,  dfs + memo</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    
<span class="hljs-meta">    @lru_cache(None)</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> p==<span class="hljs-string">""</span>: <span class="hljs-keyword">return</span> s==<span class="hljs-string">""</span>
        <span class="hljs-keyword">if</span> len(p)&gt;<span class="hljs-number">1</span> <span class="hljs-keyword">and</span> p[<span class="hljs-number">1</span>]==<span class="hljs-string">"*"</span>:<span class="hljs-keyword">return</span> self.match_star(p[<span class="hljs-number">0</span>], p[<span class="hljs-number">2</span>:], s)
        <span class="hljs-keyword">if</span> p <span class="hljs-keyword">and</span> s <span class="hljs-keyword">and</span> (p[<span class="hljs-number">0</span>]==<span class="hljs-string">"."</span> <span class="hljs-keyword">or</span> p[<span class="hljs-number">0</span>]==s[<span class="hljs-number">0</span>]): <span class="hljs-keyword">return</span> self.isMatch(s[<span class="hljs-number">1</span>:], p[<span class="hljs-number">1</span>:])
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
    
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">match_star</span><span class="hljs-params">(self, c, p, s)</span>:</span>
        <span class="hljs-keyword">if</span> self.isMatch(s,p):
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">while</span> <span class="hljs-literal">True</span>:
            <span class="hljs-keyword">if</span> self.isMatch(s,p):
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> s <span class="hljs-keyword">and</span> (c==<span class="hljs-string">"."</span> <span class="hljs-keyword">or</span> c==s[<span class="hljs-number">0</span>]):
                s = s[<span class="hljs-number">1</span>:]
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">break</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<h2 id="12-20191016-的新版本-from-top-to-down-dfs--memo">1.2 20191016 的新版本, from top to down,  dfs + memo</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    
<span class="hljs-meta">    @lru_cache(None)</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> s == <span class="hljs-string">""</span> <span class="hljs-keyword">and</span> p == <span class="hljs-string">""</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        
        <span class="hljs-keyword">if</span> len(p) &gt; <span class="hljs-number">1</span> <span class="hljs-keyword">and</span> p[<span class="hljs-number">1</span>] == <span class="hljs-string">"*"</span>:
            <span class="hljs-keyword">if</span> s <span class="hljs-keyword">and</span> (p[<span class="hljs-number">0</span>] == <span class="hljs-string">"."</span> <span class="hljs-keyword">or</span> p[<span class="hljs-number">0</span>] == s[<span class="hljs-number">0</span>]):
                <span class="hljs-keyword">if</span> self.isMatch(s[<span class="hljs-number">1</span>:], p[<span class="hljs-number">2</span>:]):  <span class="hljs-comment"># match one</span>
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                <span class="hljs-keyword">if</span> self.isMatch(s[<span class="hljs-number">1</span>:], p):   <span class="hljs-comment"># match many</span>
                    <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
            <span class="hljs-keyword">if</span> self.isMatch(s, p[<span class="hljs-number">2</span>:]):  <span class="hljs-comment"># match zero</span>
                <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
        <span class="hljs-keyword">elif</span> s <span class="hljs-keyword">and</span> p <span class="hljs-keyword">and</span> (p[<span class="hljs-number">0</span>] == <span class="hljs-string">"."</span> <span class="hljs-keyword">or</span> p[<span class="hljs-number">0</span>] == s[<span class="hljs-number">0</span>]):
            <span class="hljs-keyword">return</span> self.isMatch(s[<span class="hljs-number">1</span>:], p[<span class="hljs-number">1</span>:])
        <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
</div></code></pre>
<h2 id="13-from-bottom-to-top-dp">1.3 from bottom to top, dp</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=l3hda49XcDE&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=14">https://www.youtube.com/watch?v=l3hda49XcDE&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=14</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/RegexMatching.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/RegexMatching.java</a></li>
</ul>
<p>如下图， 横坐标是pattern = &quot;xa*b.c&quot;, 纵坐标是text = &quot;xaabyc&quot;</p>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp8.png" alt="dp8.png"></p>
<pre><code class="language-java"><div>    <span class="hljs-comment">/**
     * Dynamic programming technique for regex matching.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">matchRegex</span><span class="hljs-params">(<span class="hljs-keyword">char</span>[] text, <span class="hljs-keyword">char</span>[] pattern)</span> </span>{
        <span class="hljs-keyword">boolean</span> T[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">boolean</span>[text.length + <span class="hljs-number">1</span>][pattern.length + <span class="hljs-number">1</span>];

        T[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-keyword">true</span>;
        <span class="hljs-comment">//Deals with patterns like a* or a*b* or a*b*c*</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; T[<span class="hljs-number">0</span>].length; i++) {
            <span class="hljs-keyword">if</span> (pattern[i-<span class="hljs-number">1</span>] == <span class="hljs-string">'*'</span>) {
                T[<span class="hljs-number">0</span>][i] = T[<span class="hljs-number">0</span>][i - <span class="hljs-number">2</span>];
            }
        }

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; T.length; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>; j &lt; T[<span class="hljs-number">0</span>].length; j++) {
                <span class="hljs-keyword">if</span> (pattern[j - <span class="hljs-number">1</span>] == <span class="hljs-string">'.'</span> || pattern[j - <span class="hljs-number">1</span>] == text[i - <span class="hljs-number">1</span>]) {
                    T[i][j] = T[i-<span class="hljs-number">1</span>][j-<span class="hljs-number">1</span>];
                } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (pattern[j - <span class="hljs-number">1</span>] == <span class="hljs-string">'*'</span>)  {
                    T[i][j] = T[i][j - <span class="hljs-number">2</span>];
                    <span class="hljs-keyword">if</span> (pattern[j-<span class="hljs-number">2</span>] == <span class="hljs-string">'.'</span> || pattern[j - <span class="hljs-number">2</span>] == text[i - <span class="hljs-number">1</span>]) {
                        T[i][j] = T[i][j] | T[i - <span class="hljs-number">1</span>][j];
                    }
                } <span class="hljs-keyword">else</span> {
                    T[i][j] = <span class="hljs-keyword">false</span>;
                }
            }
        }
        <span class="hljs-keyword">return</span> T[text.length][pattern.length];
    }
</div></code></pre>
<p>我按照这个思路，写的python代码.  和Tushare roy比起来，多处理了case 2， 后来仔细想了想， case 2分支处理可以不要的。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isMatch</span><span class="hljs-params">(self, s: str, p: str)</span> -&gt; bool:</span>
        <span class="hljs-keyword">if</span> s==<span class="hljs-literal">None</span> <span class="hljs-keyword">or</span> p==<span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        
        m = len(s)
        n = len(p)
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]
        dp[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = <span class="hljs-literal">True</span>
        
        <span class="hljs-comment"># Deals with patterns like a* or a*b* or a*b*c*</span>
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">if</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>:
                dp[<span class="hljs-number">0</span>][j] = dp[<span class="hljs-number">0</span>][j<span class="hljs-number">-2</span>]
        
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> s[i<span class="hljs-number">-1</span>] == p[j<span class="hljs-number">-1</span>] <span class="hljs-keyword">or</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"."</span>:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">elif</span> p[j<span class="hljs-number">-1</span>] == <span class="hljs-string">"*"</span>: 
                    <span class="hljs-keyword">if</span> dp[i][j<span class="hljs-number">-2</span>]:  <span class="hljs-comment"># case 1:  x* match 0 x</span>
                        dp[i][j] = <span class="hljs-literal">True</span>
                    <span class="hljs-keyword">elif</span> s[i<span class="hljs-number">-1</span>] == p[j<span class="hljs-number">-2</span>] <span class="hljs-keyword">or</span> p[j<span class="hljs-number">-2</span>] == <span class="hljs-string">"."</span>:
                        <span class="hljs-keyword">if</span> dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-2</span>] == <span class="hljs-literal">True</span>:  <span class="hljs-comment"># case 2: x* match 1 x</span>
                            dp[i][j] = <span class="hljs-literal">True</span>
                        <span class="hljs-keyword">elif</span> dp[i<span class="hljs-number">-1</span>][j] == <span class="hljs-literal">True</span>: <span class="hljs-comment"># case 3: x* match multi x</span>
                            dp[i][j] = <span class="hljs-literal">True</span>
        <span class="hljs-comment">#pprint(dp)                    </span>
        <span class="hljs-keyword">return</span> dp[m][n]
    
                
                    
</div></code></pre>
<h1 id="测试用例">测试用例</h1>
<pre><code><code><div>&quot;mississippi&quot;
&quot;mis*is*p*.&quot;

</div></code></code></pre>

    </body>
    </html>